Search Results

Documents authored by Speckmann, Bettina

Document
DOI: 10.4230/LIPIcs.DISC.2023.27
Fast Reconfiguration for Programmable Matter

Authors: Irina Kostitsyna, Tom Peters, and Bettina Speckmann

Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)

Abstract
The concept of programmable matter envisions a very large number of tiny and simple robot particles forming a smart material. Even though the particles are restricted to local communication, local movement, and simple computation, their actions can nevertheless result in the global change of the material’s physical properties and geometry. A fundamental algorithmic task for programmable matter is to achieve global shape reconfiguration by specifying local behavior of the particles. In this paper we describe a new approach for shape reconfiguration in the amoebot model. The amoebot model is a distributed model which significantly restricts memory, computing, and communication capacity of the individual particles. Thus the challenge lies in coordinating the actions of particles to produce the desired behavior of the global system. Our reconfiguration algorithm is the first algorithm that does not use a canonical intermediate configuration when transforming between arbitrary shapes. We introduce new geometric primitives for amoebots and show how to reconfigure particle systems, using these primitives, in a linear number of activation rounds in the worst case. In practice, our method exploits the geometry of the symmetric difference between input and output shape: it minimizes unnecessary disassembly and reassembly of the particle system when the symmetric difference between the initial and the target shapes is small. Furthermore, our reconfiguration algorithm moves the particles over as many parallel shortest paths as the problem instance allows.
Cite as

Irina Kostitsyna, Tom Peters, and Bettina Speckmann. Fast Reconfiguration for Programmable Matter. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 27:1-27:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{kostitsyna_et_al:LIPIcs.DISC.2023.27,
  author =	{Kostitsyna, Irina and Peters, Tom and Speckmann, Bettina},
  title =	{{Fast Reconfiguration for Programmable Matter}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{27:1--27:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-301-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{281},
  editor =	{Oshman, Rotem},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.27},
  URN =		{urn:nbn:de:0030-drops-191533},
  doi =		{10.4230/LIPIcs.DISC.2023.27},
  annote =	{Keywords: Programmable matter, amoebot model, shape reconfiguration}
}
Document
DOI: 10.4230/LIPIcs.GIScience.2023.10
Data-Spatial Layouts for Grid Maps

Authors: Nathan van Beusekom, Wouter Meulemans, Bettina Speckmann, and Jo Wood

Published in: LIPIcs, Volume 277, 12th International Conference on Geographic Information Science (GIScience 2023)

Abstract
Grid maps are a well-known technique to visualize data associated with spatial regions. A grid map assigns each region to a tile in a grid (often orthogonal or hexagonal) and then represents the associated data values within this tile. Good grid maps represent the underlying geographic space well: regions that are geographically close are close in the grid map and vice versa. Though Tobler’s law suggests that spatial proximity relates to data similarity, local variations may obscure clusters and patterns in the data. For example, there are often clear differences between urban centers and adjacent rural areas with respect to socio-economic indicators. To get a better view of the data distribution, we propose grid-map layouts that take data values into account and place regions with similar data into close proximity. In the limit, such a data layout is essentially a chart and loses all spatial meaning. We present an algorithm to create hybrid layouts, allowing for trade-offs between data values and geographic space when assigning regions to tiles. Our algorithm also handles hierarchical grid maps and allows us to focus either on data or on geographic space on different levels of the hierarchy. Leveraging our algorithm we explore the design space of (hierarchical) grid maps with a hybrid layout and their semantics.
Cite as

Nathan van Beusekom, Wouter Meulemans, Bettina Speckmann, and Jo Wood. Data-Spatial Layouts for Grid Maps. In 12th International Conference on Geographic Information Science (GIScience 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 277, pp. 10:1-10:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{vanbeusekom_et_al:LIPIcs.GIScience.2023.10,
  author =	{van Beusekom, Nathan and Meulemans, Wouter and Speckmann, Bettina and Wood, Jo},
  title =	{{Data-Spatial Layouts for Grid Maps}},
  booktitle =	{12th International Conference on Geographic Information Science (GIScience 2023)},
  pages =	{10:1--10:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-288-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{277},
  editor =	{Beecham, Roger and Long, Jed A. and Smith, Dianna and Zhao, Qunshan and Wise, Sarah},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.GIScience.2023.10},
  URN =		{urn:nbn:de:0030-drops-189052},
  doi =		{10.4230/LIPIcs.GIScience.2023.10},
  annote =	{Keywords: Grid map, algorithms, trade-offs}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2022.47
Brief Announcement: An Effective Geometric Communication Structure for Programmable Matter

Authors: Irina Kostitsyna, Tom Peters, and Bettina Speckmann

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract
The concept of programmable matter envisions a very large number of tiny and simple robot particles forming a smart material that can change its physical properties and shape based on the outcome of computation and movement performed by the individual particles in a concurrent manner. We use geometric insights to develop a new type of shortest path tree for programmable matter systems. Our feather trees utilize geometry to allow particles and information to traverse the programmable matter structure via shortest paths even in the presence of multiple overlapping trees.
Cite as

Irina Kostitsyna, Tom Peters, and Bettina Speckmann. Brief Announcement: An Effective Geometric Communication Structure for Programmable Matter. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 47:1-47:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kostitsyna_et_al:LIPIcs.DISC.2022.47,
  author =	{Kostitsyna, Irina and Peters, Tom and Speckmann, Bettina},
  title =	{{Brief Announcement: An Effective Geometric Communication Structure for Programmable Matter}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{47:1--47:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.47},
  URN =		{urn:nbn:de:0030-drops-172386},
  doi =		{10.4230/LIPIcs.DISC.2022.47},
  annote =	{Keywords: Programmable matter, amoebot model, shape reconfiguration}
}
Document
DOI: 10.4230/DagRep.12.1.1
Mobility Data Science (Dagstuhl Seminar 22021)

Authors: Mohamed Mokbel, Mahmoud Sakr, Li Xiong, Andreas Züfle, Jussara Almeida, Taylor Anderson, Walid Aref, Gennady Andrienko, Natalia Andrienko, Yang Cao, Sanjay Chawla, Reynold Cheng, Panos Chrysanthis, Xiqi Fei, Gabriel Ghinita, Anita Graser, Dimitrios Gunopulos, Christian Jensen, Joon-Sook Kim, Kyoung-Sook Kim, Peer Kröger, John Krumm, Johannes Lauer, Amr Magdy, Mario Nascimento, Siva Ravada, Matthias Renz, Dimitris Sacharidis, Cyrus Shahabi, Flora Salim, Mohamed Sarwat, Maxime Schoemans, Bettina Speckmann, Egemen Tanin, Yannis Theodoridis, Kristian Torp, Goce Trajcevski, Marc van Kreveld, Carola Wenk, Martin Werner, Raymond Wong, Song Wu, Jianqiu Xu, Moustafa Youssef, Demetris Zeinalipour, Mengxuan Zhang, and Esteban Zimányi

Published in: Dagstuhl Reports, Volume 12, Issue 1 (2022)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 22021 "Mobility Data Science". This seminar was held January 9-14, 2022, including 47 participants from industry and academia. The goal of this Dagstuhl Seminar was to create a new research community of mobility data science in which the whole is greater than the sum of its parts by bringing together established leaders as well as promising young researchers from all fields related to mobility data science. Specifically, this report summarizes the main results of the seminar by (1) defining Mobility Data Science as a research domain, (2) by sketching its agenda in the coming years, and by (3) building a mobility data science community. (1) Mobility data science is defined as spatiotemporal data that additionally captures the behavior of moving entities (human, vehicle, animal, etc.). To understand, explain, and predict behavior, we note that a strong collaboration with research in behavioral and social sciences is needed. (2) Future research directions for mobility data science described in this report include a) mobility data acquisition and privacy, b) mobility data management and analysis, and c) applications of mobility data science. (3) We identify opportunities towards building a mobility data science community, towards collaborations between academic and industry, and towards a mobility data science curriculum.
Cite as

Mohamed Mokbel, Mahmoud Sakr, Li Xiong, Andreas Züfle, Jussara Almeida, Taylor Anderson, Walid Aref, Gennady Andrienko, Natalia Andrienko, Yang Cao, Sanjay Chawla, Reynold Cheng, Panos Chrysanthis, Xiqi Fei, Gabriel Ghinita, Anita Graser, Dimitrios Gunopulos, Christian Jensen, Joon-Sook Kim, Kyoung-Sook Kim, Peer Kröger, John Krumm, Johannes Lauer, Amr Magdy, Mario Nascimento, Siva Ravada, Matthias Renz, Dimitris Sacharidis, Cyrus Shahabi, Flora Salim, Mohamed Sarwat, Maxime Schoemans, Bettina Speckmann, Egemen Tanin, Yannis Theodoridis, Kristian Torp, Goce Trajcevski, Marc van Kreveld, Carola Wenk, Martin Werner, Raymond Wong, Song Wu, Jianqiu Xu, Moustafa Youssef, Demetris Zeinalipour, Mengxuan Zhang, and Esteban Zimányi. Mobility Data Science (Dagstuhl Seminar 22021). In Dagstuhl Reports, Volume 12, Issue 1, pp. 1-34, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@Article{mokbel_et_al:DagRep.12.1.1,
  author =	{Mokbel, Mohamed and Sakr, Mahmoud and Xiong, Li and Z\"{u}fle, Andreas and Almeida, Jussara and Anderson, Taylor and Aref, Walid and Andrienko, Gennady and Andrienko, Natalia and Cao, Yang and Chawla, Sanjay and Cheng, Reynold and Chrysanthis, Panos and Fei, Xiqi and Ghinita, Gabriel and Graser, Anita and Gunopulos, Dimitrios and Jensen, Christian and Kim, Joon-Sook and Kim, Kyoung-Sook and Kr\"{o}ger, Peer and Krumm, John and Lauer, Johannes and Magdy, Amr and Nascimento, Mario and Ravada, Siva and Renz, Matthias and Sacharidis, Dimitris and Shahabi, Cyrus and Salim, Flora and Sarwat, Mohamed and Schoemans, Maxime and Speckmann, Bettina and Tanin, Egemen and Theodoridis, Yannis and Torp, Kristian and Trajcevski, Goce and van Kreveld, Marc and Wenk, Carola and Werner, Martin and Wong, Raymond and Wu, Song and Xu, Jianqiu and Youssef, Moustafa and Zeinalipour, Demetris and Zhang, Mengxuan and Zim\'{a}nyi, Esteban},
  title =	{{Mobility Data Science (Dagstuhl Seminar 22021)}},
  pages =	{1--34},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2022},
  volume =	{12},
  number =	{1},
  editor =	{Mokbel, Mohamed and Sakr, Mahmoud and Xiong, Li and Z\"{u}fle, Andreas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.12.1.1},
  URN =		{urn:nbn:de:0030-drops-169190},
  doi =		{10.4230/DagRep.12.1.1},
  annote =	{Keywords: Spatio-temporal, Tracking, Privacy, Behavior, Data cleaning, Data management, Analytics}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2022.4
Compacting Squares: Input-Sensitive In-Place Reconfiguration of Sliding Squares

Authors: Hugo A. Akitaya, Erik D. Demaine, Matias Korman, Irina Kostitsyna, Irene Parada, Willem Sonke, Bettina Speckmann, Ryuhei Uehara, and Jules Wulms

Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)

Abstract
Edge-connected configurations of square modules, which can reconfigure through so-called sliding moves, are a well-established theoretical model for modular robots in two dimensions. Dumitrescu and Pach [Graphs and Combinatorics, 2006] proved that it is always possible to reconfigure one edge-connected configuration of n squares into any other using at most O(n²) sliding moves, while keeping the configuration connected at all times. For certain pairs of configurations, reconfiguration may require Ω(n²) sliding moves. However, significantly fewer moves may be sufficient. We prove that it is NP-hard to minimize the number of sliding moves for a given pair of edge-connected configurations. On the positive side we present Gather&Compact, an input-sensitive in-place algorithm that requires only O( ̄P n) sliding moves to transform one configuration into the other, where ̄P is the maximum perimeter of the two bounding boxes. The squares move within the bounding boxes only, with the exception of at most one square at a time which may move through the positions adjacent to the bounding boxes. The O( ̄P n) bound never exceeds O(n²), and is optimal (up to constant factors) among all bounds parameterized by just n and ̄P. Our algorithm is built on the basic principle that well-connected components of modular robots can be transformed efficiently. Hence we iteratively increase the connectivity within a configuration, to finally arrive at a single solid xy-monotone component. We implemented Gather&Compact and compared it experimentally to the in-place modification by Moreno and Sacristán [EuroCG 2020] of the Dumitrescu and Pach algorithm (MSDP). Our experiments show that Gather&Compact consistently outperforms MSDP by a significant margin, on all types of square configurations.
Cite as

Hugo A. Akitaya, Erik D. Demaine, Matias Korman, Irina Kostitsyna, Irene Parada, Willem Sonke, Bettina Speckmann, Ryuhei Uehara, and Jules Wulms. Compacting Squares: Input-Sensitive In-Place Reconfiguration of Sliding Squares. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 4:1-4:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{a.akitaya_et_al:LIPIcs.SWAT.2022.4,
  author =	{A. Akitaya, Hugo and Demaine, Erik D. and Korman, Matias and Kostitsyna, Irina and Parada, Irene and Sonke, Willem and Speckmann, Bettina and Uehara, Ryuhei and Wulms, Jules},
  title =	{{Compacting Squares: Input-Sensitive In-Place Reconfiguration of Sliding Squares}},
  booktitle =	{18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
  pages =	{4:1--4:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-236-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{227},
  editor =	{Czumaj, Artur and Xin, Qin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.4},
  URN =		{urn:nbn:de:0030-drops-161644},
  doi =		{10.4230/LIPIcs.SWAT.2022.4},
  annote =	{Keywords: Sliding cubes, Reconfiguration, Modular robots, NP-hardness}
}
Document
DOI: 10.4230/LIPIcs.GIScience.2021.II.7
Coordinated Schematization for Visualizing Mobility Patterns on Networks

Authors: Bram Custers, Wouter Meulemans, Bettina Speckmann, and Kevin Verbeek

Published in: LIPIcs, Volume 208, 11th International Conference on Geographic Information Science (GIScience 2021) - Part II

Abstract
GPS trajectories of vehicles moving on a road network are a valuable source of traffic information. However, the sheer volume of available data makes it challenging to identify and visualize salient patterns. Meaningful visual summaries of trajectory collections require that both the trajectories and the underlying network are aggregated and simplified in a coherent manner. In this paper we propose a coordinated fully-automated pipeline for computing a schematic overview of mobility patterns from a collection of trajectories on a street network. Our pipeline utilizes well-known building blocks from GIS, automated cartography, and trajectory analysis: map matching, road selection, schematization, movement patterns, and metro-map style rendering. We showcase the results of our pipeline on two real-world trajectory collections around The Hague and Beijing.
Cite as

Bram Custers, Wouter Meulemans, Bettina Speckmann, and Kevin Verbeek. Coordinated Schematization for Visualizing Mobility Patterns on Networks. In 11th International Conference on Geographic Information Science (GIScience 2021) - Part II. Leibniz International Proceedings in Informatics (LIPIcs), Volume 208, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{custers_et_al:LIPIcs.GIScience.2021.II.7,
  author =	{Custers, Bram and Meulemans, Wouter and Speckmann, Bettina and Verbeek, Kevin},
  title =	{{Coordinated Schematization for Visualizing Mobility Patterns on Networks}},
  booktitle =	{11th International Conference on Geographic Information Science (GIScience 2021) - Part II},
  pages =	{7:1--7:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-208-2},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{208},
  editor =	{Janowicz, Krzysztof and Verstegen, Judith A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.GIScience.2021.II.7},
  URN =		{urn:nbn:de:0030-drops-147665},
  doi =		{10.4230/LIPIcs.GIScience.2021.II.7},
  annote =	{Keywords: Trajectories, Visualization, Schematization}
}
Document
DOI: 10.4230/LIPIcs.GIScience.2021.II.8
Harmonious Simplification of Isolines

Authors: Arthur van Goethem, Wouter Meulemans, Andreas Reimer, and Bettina Speckmann

Published in: LIPIcs, Volume 208, 11th International Conference on Geographic Information Science (GIScience 2021) - Part II

Abstract
Current techniques for simplification focus on reducing complexity while maintaining the geometric similarity to the input. For isolines that jointly describe a scalar field, however, we postulate that geometric similarity of each isoline separately is not sufficient. Rather, we need to maintain the harmony between these isolines to make them visually relate and describe the structures of the underlying terrain. Based on principles of manual cartography, we propose an algorithm for simplifying isolines while considering harmony explicitly. Our preliminary visual and quantitative results suggest that our algorithm is effective.
Cite as

Arthur van Goethem, Wouter Meulemans, Andreas Reimer, and Bettina Speckmann. Harmonious Simplification of Isolines. In 11th International Conference on Geographic Information Science (GIScience 2021) - Part II. Leibniz International Proceedings in Informatics (LIPIcs), Volume 208, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{vangoethem_et_al:LIPIcs.GIScience.2021.II.8,
  author =	{van Goethem, Arthur and Meulemans, Wouter and Reimer, Andreas and Speckmann, Bettina},
  title =	{{Harmonious Simplification of Isolines}},
  booktitle =	{11th International Conference on Geographic Information Science (GIScience 2021) - Part II},
  pages =	{8:1--8:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-208-2},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{208},
  editor =	{Janowicz, Krzysztof and Verstegen, Judith A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.GIScience.2021.II.8},
  URN =		{urn:nbn:de:0030-drops-147675},
  doi =		{10.4230/LIPIcs.GIScience.2021.II.8},
  annote =	{Keywords: Simplification, isolines, harmony}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2021.56
Obstructing Classification via Projection

Authors: Pantea Haghighatkhah, Wouter Meulemans, Bettina Speckmann, Jérôme Urhausen, and Kevin Verbeek

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract
Machine learning and data mining techniques are effective tools to classify large amounts of data. But they tend to preserve any inherent bias in the data, for example, with regards to gender or race. Removing such bias from data or the learned representations is quite challenging. In this paper we study a geometric problem which models a possible approach for bias removal. Our input is a set of points P in Euclidean space ℝ^d and each point is labeled with k binary-valued properties. A priori we assume that it is "easy" to classify the data according to each property. Our goal is to obstruct the classification according to one property by a suitable projection to a lower-dimensional Euclidean space ℝ^m (m < d), while classification according to all other properties remains easy. What it means for classification to be easy depends on the classification model used. We first consider classification by linear separability as employed by support vector machines. We use Kirchberger’s Theorem to show that, under certain conditions, a simple projection to ℝ^{d-1} suffices to eliminate the linear separability of one of the properties whilst maintaining the linear separability of the other properties. We also study the problem of maximizing the linear "inseparability" of the chosen property. Second, we consider more complex forms of separability and prove a connection between the number of projections required to obstruct classification and the Helly-type properties of such separabilities.
Cite as

Pantea Haghighatkhah, Wouter Meulemans, Bettina Speckmann, Jérôme Urhausen, and Kevin Verbeek. Obstructing Classification via Projection. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 56:1-56:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{haghighatkhah_et_al:LIPIcs.MFCS.2021.56,
  author =	{Haghighatkhah, Pantea and Meulemans, Wouter and Speckmann, Bettina and Urhausen, J\'{e}r\^{o}me and Verbeek, Kevin},
  title =	{{Obstructing Classification via Projection}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{56:1--56:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.56},
  URN =		{urn:nbn:de:0030-drops-144965},
  doi =		{10.4230/LIPIcs.MFCS.2021.56},
  annote =	{Keywords: Projection, classification, models of learning}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2021.55
Polygon-Universal Graphs

Authors: Tim Ophelders, Ignaz Rutter, Bettina Speckmann, and Kevin Verbeek

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract
We study a fundamental question from graph drawing: given a pair (G,C) of a graph G and a cycle C in G together with a simple polygon P, is there a straight-line drawing of G inside P which maps C to P? We say that such a drawing of (G,C) respects P. We fully characterize those instances (G,C) which are polygon-universal, that is, they have a drawing that respects P for any simple (not necessarily convex) polygon P. Specifically, we identify two necessary conditions for an instance to be polygon-universal. Both conditions are based purely on graph and cycle distances and are easy to check. We show that these two conditions are also sufficient. Furthermore, if an instance (G,C) is planar, that is, if there exists a planar drawing of G with C on the outer face, we show that the same conditions guarantee for every simple polygon P the existence of a planar drawing of (G,C) that respects P. If (G,C) is polygon-universal, then our proofs directly imply a linear-time algorithm to construct a drawing that respects a given polygon P.
Cite as

Tim Ophelders, Ignaz Rutter, Bettina Speckmann, and Kevin Verbeek. Polygon-Universal Graphs. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 55:1-55:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{ophelders_et_al:LIPIcs.SoCG.2021.55,
  author =	{Ophelders, Tim and Rutter, Ignaz and Speckmann, Bettina and Verbeek, Kevin},
  title =	{{Polygon-Universal Graphs}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{55:1--55:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.55},
  URN =		{urn:nbn:de:0030-drops-138540},
  doi =		{10.4230/LIPIcs.SoCG.2021.55},
  annote =	{Keywords: Graph drawing, partial drawing extension, simple polygon}
}
Document
DOI: 10.4230/LIPIcs.GIScience.2021.I.16
Volume from Outlines on Terrains

Authors: Marc van Kreveld, Tim Ophelders, Willem Sonke, Bettina Speckmann, and Kevin Verbeek

Published in: LIPIcs, Volume 177, 11th International Conference on Geographic Information Science (GIScience 2021) - Part I (2020)

Abstract
Outlines (closed loops) delineate areas of interest on terrains, such as regions with a heightened risk of landslides. For various analysis tasks it is necessary to define and compute a volume of earth (soil) based on such an outline, capturing, for example, the possible volume of a landslide in a high-risk region. In this paper we discuss several options to define meaningful 2D surfaces induced by a 1D outline, which allow us to compute such volumes. We experimentally compare the proposed surface options for two applications: similarity of paths on terrains and landslide susceptibility analysis.
Cite as

Marc van Kreveld, Tim Ophelders, Willem Sonke, Bettina Speckmann, and Kevin Verbeek. Volume from Outlines on Terrains. In 11th International Conference on Geographic Information Science (GIScience 2021) - Part I. Leibniz International Proceedings in Informatics (LIPIcs), Volume 177, pp. 16:1-16:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{vankreveld_et_al:LIPIcs.GIScience.2021.I.16,
  author =	{van Kreveld, Marc and Ophelders, Tim and Sonke, Willem and Speckmann, Bettina and Verbeek, Kevin},
  title =	{{Volume from Outlines on Terrains}},
  booktitle =	{11th International Conference on Geographic Information Science (GIScience 2021) - Part I},
  pages =	{16:1--16:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-166-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{177},
  editor =	{Janowicz, Krzysztof and Verstegen, Judith A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.GIScience.2021.I.16},
  URN =		{urn:nbn:de:0030-drops-130512},
  doi =		{10.4230/LIPIcs.GIScience.2021.I.16},
  annote =	{Keywords: Terrain model, similarity, volume, computation}
}
Document
Media Exposition
DOI: 10.4230/LIPIcs.SoCG.2020.78
Hiding Sliding Cubes: Why Reconfiguring Modular Robots Is Not Easy (Media Exposition)

Authors: Tillmann Miltzow, Irene Parada, Willem Sonke, Bettina Speckmann, and Jules Wulms

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
Face-connected configurations of cubes are a common model for modular robots in three dimensions. In this abstract and the accompanying video we study reconfigurations of such modular robots using so-called sliding moves. Using sliding moves, it is always possible to reconfigure one face-connected configuration of n cubes into any other, while keeping the robot connected at all stages of the reconfiguration. For certain configurations Ω(n²) sliding moves are necessary. In contrast, the best current upper bound is O(n³). It has been conjectured that there is always a cube on the outside of any face-connected configuration of cubes which can be moved without breaking connectivity. The existence of such a cube would immediately imply a straight-forward O(n²) reconfiguration algorithm. However, we present a configuration of cubes such that no cube on the outside can move without breaking connectivity. In other words, we show that this particular avenue towards an O(n²) reconfiguration algorithm for face-connected cubes is blocked.
Cite as

Tillmann Miltzow, Irene Parada, Willem Sonke, Bettina Speckmann, and Jules Wulms. Hiding Sliding Cubes: Why Reconfiguring Modular Robots Is Not Easy (Media Exposition). In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 78:1-78:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{miltzow_et_al:LIPIcs.SoCG.2020.78,
  author =	{Miltzow, Tillmann and Parada, Irene and Sonke, Willem and Speckmann, Bettina and Wulms, Jules},
  title =	{{Hiding Sliding Cubes: Why Reconfiguring Modular Robots Is Not Easy}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{78:1--78:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.78},
  URN =		{urn:nbn:de:0030-drops-122363},
  doi =		{10.4230/LIPIcs.SoCG.2020.78},
  annote =	{Keywords: Sliding cubes, Reconfiguration, Modular robots}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2019.42
Preprocessing Ambiguous Imprecise Points

Authors: Ivor van der Hoog, Irina Kostitsyna, Maarten Löffler, and Bettina Speckmann

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

Abstract
Let R = {R_1, R_2, ..., R_n} be a set of regions and let X = {x_1, x_2, ..., x_n} be an (unknown) point set with x_i in R_i. Region R_i represents the uncertainty region of x_i. We consider the following question: how fast can we establish order if we are allowed to preprocess the regions in R? The preprocessing model of uncertainty uses two consecutive phases: a preprocessing phase which has access only to R followed by a reconstruction phase during which a desired structure on X is computed. Recent results in this model parametrize the reconstruction time by the ply of R, which is the maximum overlap between the regions in R. We introduce the ambiguity A(R) as a more fine-grained measure of the degree of overlap in R. We show how to preprocess a set of d-dimensional disks in O(n log n) time such that we can sort X (if d=1) and reconstruct a quadtree on X (if d >= 1 but constant) in O(A(R)) time. If A(R) is sub-linear, then reporting the result dominates the running time of the reconstruction phase. However, we can still return a suitable data structure representing the result in O(A(R)) time. In one dimension, {R} is a set of intervals and the ambiguity is linked to interval entropy, which in turn relates to the well-studied problem of sorting under partial information. The number of comparisons necessary to find the linear order underlying a poset P is lower-bounded by the graph entropy of P. We show that if P is an interval order, then the ambiguity provides a constant-factor approximation of the graph entropy. This gives a lower bound of Omega(A(R)) in all dimensions for the reconstruction phase (sorting or any proximity structure), independent of any preprocessing; hence our result is tight. Finally, our results imply that one can approximate the entropy of interval graphs in O(n log n) time, improving the O(n^{2.5}) bound by Cardinal et al.
Cite as

Ivor van der Hoog, Irina Kostitsyna, Maarten Löffler, and Bettina Speckmann. Preprocessing Ambiguous Imprecise Points. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 42:1-42:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{vanderhoog_et_al:LIPIcs.SoCG.2019.42,
  author =	{van der Hoog, Ivor and Kostitsyna, Irina and L\"{o}ffler, Maarten and Speckmann, Bettina},
  title =	{{Preprocessing Ambiguous Imprecise Points}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{42:1--42:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.42},
  URN =		{urn:nbn:de:0030-drops-104460},
  doi =		{10.4230/LIPIcs.SoCG.2019.42},
  annote =	{Keywords: preprocessing, imprecise points, entropy, sorting, proximity structures}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.SoCG.2018
LIPIcs, Volume 99, SoCG'18, Complete Volume

Authors: Bettina Speckmann and Csaba D. Tóth

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract
LIPIcs, Volume 99, SoCG'18, Complete Volume
Cite as

34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Proceedings{speckmann_et_al:LIPIcs.SoCG.2018,
  title =	{{LIPIcs, Volume 99, SoCG'18, Complete Volume}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018},
  URN =		{urn:nbn:de:0030-drops-89308},
  doi =		{10.4230/LIPIcs.SoCG.2018},
  annote =	{Keywords: Theory of computation, Computational geometry, Mathematics of computing, Combinatorics, Theory of computation, Design and analysis of algorithms}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.SoCG.2018.0
Front Matter, Table of Contents, Foreword, Conference Organization, Additional Reviewers, Acknowledgement of Support, Invited Talks

Authors: Bettina Speckmann and Csaba D. Tóth

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract
Front Matter, Table of Contents, Foreword, Conference Organization, Additional Reviewers, Acknowledgement of Support, Invited Talks
Cite as

34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 0:i-0:xi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{speckmann_et_al:LIPIcs.SoCG.2018.0,
  author =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  title =	{{Front Matter, Table of Contents, Foreword, Conference Organization, Additional Reviewers, Acknowledgement of Support, Invited Talks}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{0:i--0:xi},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.0},
  URN =		{urn:nbn:de:0030-drops-87136},
  doi =		{10.4230/LIPIcs.SoCG.2018.0},
  annote =	{Keywords: Front Matter, Table of Contents, Foreword, Conference Organization, Additional Reviewers, Acknowledgement of Support, Invited Talks}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2017.54
Non-Crossing Geometric Steiner Arborescences

Authors: Irina Kostitsyna, Bettina Speckmann, and Kevin Verbeek

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Abstract
Motivated by the question of simultaneous embedding of several flow maps, we consider the problem of drawing multiple geometric Steiner arborescences with no crossings in the rectilinear and in the angle-restricted setting. When terminal-to-root paths are allowed to turn freely, we show that two rectilinear Steiner arborescences have a non-crossing drawing if neither tree necessarily completely disconnects the other tree and if the roots of both trees are "free". If the roots are not free, then we can reduce the decision problem to 2SAT. If terminal-to-root paths are allowed to turn only at Steiner points, then it is NP-hard to decide whether multiple rectilinear Steiner arborescences have a non-crossing drawing. The setting of angle-restricted Steiner arborescences is more subtle than the rectilinear case. Our NP-hardness result extends, but testing whether there exists a non-crossing drawing if the roots of both trees are free requires additional conditions to be fulfilled.
Cite as

Irina Kostitsyna, Bettina Speckmann, and Kevin Verbeek. Non-Crossing Geometric Steiner Arborescences. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 54:1-54:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{kostitsyna_et_al:LIPIcs.ISAAC.2017.54,
  author =	{Kostitsyna, Irina and Speckmann, Bettina and Verbeek, Kevin},
  title =	{{Non-Crossing Geometric Steiner Arborescences}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{54:1--54:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.54},
  URN =		{urn:nbn:de:0030-drops-82342},
  doi =		{10.4230/LIPIcs.ISAAC.2017.54},
  annote =	{Keywords: Steiner arborescences, non-crossing drawing, rectilinear, angle-restricted}
}
Document
DOI: 10.4230/LIPIcs.ESA.2017.23
Computing Optimal Homotopies over a Spiked Plane with Polygonal Boundary

Authors: Benjamin Burton, Erin Chambers, Marc van Kreveld, Wouter Meulemans, Tim Ophelders, and Bettina Speckmann

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

Abstract
Computing optimal deformations between two curves is a fundamental question with various applications, and has recently received much attention in both computational topology and in mathematics in the form of homotopies of disks and annular regions. In this paper, we examine this problem in a geometric setting, where we consider the boundary of a polygonal domain with spikes, point obstacles that can be crossed at an additive cost. We aim to continuously morph from one part of the boundary to another, necessarily passing over all spikes, such that the most expensive intermediate curve is minimized, where the cost of a curve is its geometric length plus the cost of any spikes it crosses. We first investigate the general setting where each spike may have a different cost. For the number of inflection points in an intermediate curve, we present a lower bound that is linear in the number of spikes, even if the domain is convex and the two boundaries for which we seek a morph share an endpoint. We describe a 2-approximation algorithm for the general case, and an optimal algorithm for the case that the two boundaries for which we seek a morph share both endpoints, thereby representing the entire boundary of the domain. We then consider the setting where all spikes have the same unit cost and we describe a polynomial-time exact algorithm. The algorithm combines structural properties of homotopies arising from the geometry with methodology for computing Fréchet distances.
Cite as

Benjamin Burton, Erin Chambers, Marc van Kreveld, Wouter Meulemans, Tim Ophelders, and Bettina Speckmann. Computing Optimal Homotopies over a Spiked Plane with Polygonal Boundary. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 23:1-23:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{burton_et_al:LIPIcs.ESA.2017.23,
  author =	{Burton, Benjamin and Chambers, Erin and van Kreveld, Marc and Meulemans, Wouter and Ophelders, Tim and Speckmann, Bettina},
  title =	{{Computing Optimal Homotopies over a Spiked Plane with Polygonal Boundary}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{23:1--23:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.23},
  URN =		{urn:nbn:de:0030-drops-78630},
  doi =		{10.4230/LIPIcs.ESA.2017.23},
  annote =	{Keywords: Fr\'{e}chet distance, polygonal domain, homotopy, geodesic, obstacle}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2017.48
Computing Representative Networks for Braided Rivers

Authors: Maarten Kleinhans, Marc van Kreveld, Tim Ophelders, Willem Sonke, Bettina Speckmann, and Kevin Verbeek

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract
Drainage networks on terrains have been studied extensively from an algorithmic perspective. However, in drainage networks water flow cannot bifurcate and hence they do not model braided rivers (multiple channels which split and join, separated by sediment bars). We initiate the algorithmic study of braided rivers by employing the descending quasi Morse-Smale complex on the river bed (a polyhedral terrain), and extending it with a certain ordering of bars from the one river bank to the other. This allows us to compute a graph that models a representative channel network, consisting of lowest paths. To ensure that channels in this network are sufficiently different we define a sand function that represents the volume of sediment separating them. We show that in general the problem of computing a maximum network of non-crossing channels which are delta-different from each other (as measured by the sand function) is NP-hard. However, using our ordering between the river banks, we can compute a maximum delta-different network that respects this order in polynomial time. We implemented our approach and applied it to simulated and real-world braided rivers.
Cite as

Maarten Kleinhans, Marc van Kreveld, Tim Ophelders, Willem Sonke, Bettina Speckmann, and Kevin Verbeek. Computing Representative Networks for Braided Rivers. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 48:1-48:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{kleinhans_et_al:LIPIcs.SoCG.2017.48,
  author =	{Kleinhans, Maarten and van Kreveld, Marc and Ophelders, Tim and Sonke, Willem and Speckmann, Bettina and Verbeek, Kevin},
  title =	{{Computing Representative Networks for Braided Rivers}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{48:1--48:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.48},
  URN =		{urn:nbn:de:0030-drops-72204},
  doi =		{10.4230/LIPIcs.SoCG.2017.48},
  annote =	{Keywords: braided rivers, Morse-Smale complex, persistence, network extraction, polyhedral terrain}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.7
An Improved Lower Bound on the Minimum Number of Triangulations

Authors: Oswin Aichholzer, Victor Alvarez, Thomas Hackl, Alexander Pilz, Bettina Speckmann, and Birgit Vogtenhuber

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
Upper and lower bounds for the number of geometric graphs of specific types on a given set of points in the plane have been intensively studied in recent years. For most classes of geometric graphs it is now known that point sets in convex position minimize their number. However, it is still unclear which point sets minimize the number of geometric triangulations; the so-called double circles are conjectured to be the minimizing sets. In this paper we prove that any set of n points in general position in the plane has at least Omega(2.631^n) geometric triangulations. Our result improves the previously best general lower bound of Omega(2.43^n) and also covers the previously best lower bound of Omega(2.63^n) for a fixed number of extreme points. We achieve our bound by showing and combining several new results, which are of independent interest: (1) Adding a point on the second convex layer of a given point set (of 7 or more points) at least doubles the number of triangulations. (2) Generalized configurations of points that minimize the number of triangulations have at most n/2 points on their convex hull. (3) We provide tight lower bounds for the number of triangulations of point sets with up to 15 points. These bounds further support the double circle conjecture.
Cite as

Oswin Aichholzer, Victor Alvarez, Thomas Hackl, Alexander Pilz, Bettina Speckmann, and Birgit Vogtenhuber. An Improved Lower Bound on the Minimum Number of Triangulations. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{aichholzer_et_al:LIPIcs.SoCG.2016.7,
  author =	{Aichholzer, Oswin and Alvarez, Victor and Hackl, Thomas and Pilz, Alexander and Speckmann, Bettina and Vogtenhuber, Birgit},
  title =	{{An Improved Lower Bound on the Minimum Number of Triangulations}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{7:1--7:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.7},
  URN =		{urn:nbn:de:0030-drops-58993},
  doi =		{10.4230/LIPIcs.SoCG.2016.7},
  annote =	{Keywords: Combinatorial geometry, Order types, Triangulations}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.61
Grouping Time-Varying Data for Interactive Exploration

Authors: Arthur van Goethem, Marc van Kreveld, Maarten Löffler, Bettina Speckmann, and Frank Staals

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
We present algorithms and data structures that support the interactive analysis of the grouping structure of one-, two-, or higher-dimensional time-varying data while varying all defining parameters. Grouping structures characterise important patterns in the temporal evaluation of sets of time-varying data. We follow Buchin et al. [JoCG 2015] who define groups using three parameters: group-size, group-duration, and inter-entity distance. We give upper and lower bounds on the number of maximal groups over all parameter values, and show how to compute them efficiently. Furthermore, we describe data structures that can report changes in the set of maximal groups in an output-sensitive manner. Our results hold in R^d for fixed d.
Cite as

Arthur van Goethem, Marc van Kreveld, Maarten Löffler, Bettina Speckmann, and Frank Staals. Grouping Time-Varying Data for Interactive Exploration. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 61:1-61:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{vangoethem_et_al:LIPIcs.SoCG.2016.61,
  author =	{van Goethem, Arthur and van Kreveld, Marc and L\"{o}ffler, Maarten and Speckmann, Bettina and Staals, Frank},
  title =	{{Grouping Time-Varying Data for Interactive Exploration}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{61:1--61:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.61},
  URN =		{urn:nbn:de:0030-drops-59539},
  doi =		{10.4230/LIPIcs.SoCG.2016.61},
  annote =	{Keywords: Trajectory, Time series, Moving entity, Grouping, Algorithm, Data structure}
}
Document
DOI: 10.4230/DagRep.6.1.55
Geometric and Graph-based Approaches to Collective Motion (Dagstuhl Seminar 16022)

Authors: Giuseppe F. Italiano, Marc van Kreveld, Bettina Speckmann, and Guy Theraulaz

Published in: Dagstuhl Reports, Volume 6, Issue 1 (2016)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 16022 "Geometric and Graph-based Approaches to Collective Motion". The seminar brought together a group of enthusiastic researchers with a diverse background. To create a shared body of knowledge the seminar featured a number of survey talks that were planned early in the week. The survey talks were rather engaging: the audience learned for instance at what scale one should look at a painting of Van Gogh, how bats chase each other, what size of clumps mussels make and why, and how to interact with a computational geometer.
Cite as

Giuseppe F. Italiano, Marc van Kreveld, Bettina Speckmann, and Guy Theraulaz. Geometric and Graph-based Approaches to Collective Motion (Dagstuhl Seminar 16022). In Dagstuhl Reports, Volume 6, Issue 1, pp. 55-68, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@Article{italiano_et_al:DagRep.6.1.55,
  author =	{Italiano, Giuseppe F. and van Kreveld, Marc and Speckmann, Bettina and Theraulaz, Guy},
  title =	{{Geometric and Graph-based Approaches to Collective Motion (Dagstuhl Seminar 16022)}},
  pages =	{55--68},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2016},
  volume =	{6},
  number =	{1},
  editor =	{Italiano, Giuseppe F. and van Kreveld, Marc and Speckmann, Bettina and Theraulaz, Guy},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.6.1.55},
  URN =		{urn:nbn:de:0030-drops-58095},
  doi =		{10.4230/DagRep.6.1.55},
  annote =	{Keywords: Geometry, Graph, Interaction, Motion, Pattern, Trajectory}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.674
Trajectory Grouping Structure under Geodesic Distance

Authors: Irina Kostitsyna, Marc van Kreveld, Maarten Löffler, Bettina Speckmann, and Frank Staals

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract
In recent years trajectory data has become one of the main types of geographic data, and hence algorithmic tools to handle large quantities of trajectories are essential. A single trajectory is typically represented as a sequence of time-stamped points in the plane. In a collection of trajectories one wants to detect maximal groups of moving entities and their behaviour (merges and splits) over time. This information can be summarized in the trajectory grouping structure. Significantly extending the work of Buchin et al. [WADS 2013] into a realistic setting, we show that the trajectory grouping structure can be computed efficiently also if obstacles are present and the distance between the entities is measured by geodesic distance. We bound the number of critical events: times at which the distance between two subsets of moving entities is exactly epsilon, where epsilon is the threshold distance that determines whether two entities are close enough to be in one group. In case the n entities move in a simple polygon along trajectories with tau vertices each we give an O(tau n^2) upper bound, which is tight in the worst case. In case of well-spaced obstacles we give an O(tau(n^2 + m lambda_4(n))) upper bound, where m is the total complexity of the obstacles, and lambda_s(n) denotes the maximum length of a Davenport-Schinzel sequence of n symbols of order s. In case of general obstacles we give an O(tau min(n^2 + m^3 lambda_4(n), n^2m^2)) upper bound. Furthermore, for all cases we provide efficient algorithms to compute the critical events, which in turn leads to efficient algorithms to compute the trajectory grouping structure.
Cite as

Irina Kostitsyna, Marc van Kreveld, Maarten Löffler, Bettina Speckmann, and Frank Staals. Trajectory Grouping Structure under Geodesic Distance. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 674-688, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{kostitsyna_et_al:LIPIcs.SOCG.2015.674,
  author =	{Kostitsyna, Irina and van Kreveld, Marc and L\"{o}ffler, Maarten and Speckmann, Bettina and Staals, Frank},
  title =	{{Trajectory Grouping Structure under Geodesic Distance}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{674--688},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.674},
  URN =		{urn:nbn:de:0030-drops-51212},
  doi =		{10.4230/LIPIcs.SOCG.2015.674},
  annote =	{Keywords: moving entities, trajectories, grouping, computational geometry}
}
Document
DOI: 10.4230/DagSemProc.10491.1
10491 Abstracts Collection – Representation, Analysis and Visualization of Moving Objects

Authors: Jörg-Rüdiger Sack, Bettina Speckmann, Emiel Van Loon, and Robert Weibel

Published in: Dagstuhl Seminar Proceedings, Volume 10491, Representation, Analysis and Visualization of Moving Objects (2011)

Abstract
From December 5 to December 10, 2010, the Dagstuhl Seminar 10491 ``Representation, Analysis and Visualization of Moving Objects'' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. The major goal of this seminar has been to bring together the diverse and fast growing, research community that is involved in developing better computational techniques for spatio-temporal object representation, data mining, and visualization massive amounts of moving object data. The participants included experts from fields such as computational geometry, data mining, visual analytics, GIS science, transportation science, urban planning and movement ecology. Most of the participants came from academic institutions, some from government agencies and industry. The seminar has led to a fruitful exchange of ideas between different disciplines, to the creation of new interdisciplinary collaborations, concrete plans for a data challenge in an upcoming conference, and to recommendations for future research directions. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper.
Cite as

Jörg-Rüdiger Sack, Bettina Speckmann, Emiel Van Loon, and Robert Weibel. 10491 Abstracts Collection – Representation, Analysis and Visualization of Moving Objects. In Representation, Analysis and Visualization of Moving Objects. Dagstuhl Seminar Proceedings, Volume 10491, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{sack_et_al:DagSemProc.10491.1,
  author =	{Sack, J\"{o}rg-R\"{u}diger and Speckmann, Bettina and Van Loon, Emiel and Weibel, Robert},
  title =	{{10491 Abstracts Collection – Representation, Analysis and Visualization of Moving Objects}},
  booktitle =	{Representation, Analysis and Visualization of Moving Objects},
  pages =	{1--14},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2011},
  volume =	{10491},
  editor =	{J\"{o}rg-R\"{u}diger Sack and Bettina Speckmann and Emiel Van Loon and Robert Weibel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10491.1},
  URN =		{urn:nbn:de:0030-drops-30870},
  doi =		{10.4230/DagSemProc.10491.1},
  annote =	{Keywords: Moving objects, Spatio-temporal databases, Spatio-temporal analysis, Movement analysis, Spatial data mining, KDD, Computational geometry, Visual analytics}
}
Document
DOI: 10.4230/DagSemProc.10491.2
10491 Summary – Representation, Analysis and Visualization of Moving Objects

Authors: Jörg-Rüdiger Sack, Bettina Speckmann, Emiel van Loon, and Robert Weibel

Published in: Dagstuhl Seminar Proceedings, Volume 10491, Representation, Analysis and Visualization of Moving Objects (2011)

Abstract
This seminar is a successor to the Representation, Analysis and Visualization of Moving Objects seminar in 2008 (seminar 08451). The major goal has been to bring together the diverse and fast growing, research community that is involved in developing better computational techniques for spatio-temporal object representation, data mining, and visualization of massive amounts of moving object data. The participants included experts from fields such as computational geometry, data mining, visual analytics, GIS science, transportation science, urban planning and movement ecology. Most of the participants came from academic institutions, some from government agencies and industry. The seminar has led to a fruitful exchange of ideas between different disciplines, to the creation of new interdisciplinary collaborations, concrete plans for a data challenge in an upcoming conference, and to recommendations for future research directions.
Cite as

Jörg-Rüdiger Sack, Bettina Speckmann, Emiel van Loon, and Robert Weibel. 10491 Summary – Representation, Analysis and Visualization of Moving Objects. In Representation, Analysis and Visualization of Moving Objects. Dagstuhl Seminar Proceedings, Volume 10491, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{sack_et_al:DagSemProc.10491.2,
  author =	{Sack, J\"{o}rg-R\"{u}diger and Speckmann, Bettina and van Loon, Emiel and Weibel, Robert},
  title =	{{10491 Summary – Representation, Analysis and Visualization of Moving Objects}},
  booktitle =	{Representation, Analysis and Visualization of Moving Objects},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2011},
  volume =	{10491},
  editor =	{J\"{o}rg-R\"{u}diger Sack and Bettina Speckmann and Emiel Van Loon and Robert Weibel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10491.2},
  URN =		{urn:nbn:de:0030-drops-30864},
  doi =		{10.4230/DagSemProc.10491.2},
  annote =	{Keywords: Moving objects, spatio-temporal databases, spatio-temporal analysis, movement analysis, spatial data mining, KDD, computational geometry, visual analy}
}
Document
DOI: 10.4230/DagSemProc.10491.3
10491 Results of the break-out group: Aggregation

Authors: Mark de Berg, Jörg-Rüdiger Sack, Bettina Speckmann, Anne Driemel, Maike Buchin, Monika Sester, and Marc van Kreveld

Published in: Dagstuhl Seminar Proceedings, Volume 10491, Representation, Analysis and Visualization of Moving Objects (2011)

Abstract
We discussed different problems that arise when aggregating trajectories: how to segment the input, whether to use original parts of the input trajectories, as opposed to an ``averaged'' path and how to simplify the aggregated structure. We give examples where these questions are not easily answered.
Cite as

Mark de Berg, Jörg-Rüdiger Sack, Bettina Speckmann, Anne Driemel, Maike Buchin, Monika Sester, and Marc van Kreveld. 10491 Results of the break-out group: Aggregation. In Representation, Analysis and Visualization of Moving Objects. Dagstuhl Seminar Proceedings, Volume 10491, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{deberg_et_al:DagSemProc.10491.3,
  author =	{de Berg, Mark and Sack, J\"{o}rg-R\"{u}diger and Speckmann, Bettina and Driemel, Anne and Buchin, Maike and Sester, Monika and van Kreveld, Marc},
  title =	{{10491 Results of the break-out group: Aggregation}},
  booktitle =	{Representation, Analysis and Visualization of Moving Objects},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2011},
  volume =	{10491},
  editor =	{J\"{o}rg-R\"{u}diger Sack and Bettina Speckmann and Emiel Van Loon and Robert Weibel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10491.3},
  URN =		{urn:nbn:de:0030-drops-29878},
  doi =		{10.4230/DagSemProc.10491.3},
  annote =	{Keywords: Aggregation, Trajectories, Generalization, Map Generation}
}
Document
DOI: 10.4230/DagSemProc.08081.2
Kinetic kd-Trees and Longest-Side kd-Trees

Authors: Mohammad Abam, Mark de Berg, and Bettina Speckmann

Published in: Dagstuhl Seminar Proceedings, Volume 8081, Data Structures (2008)

Abstract
We propose a simple variant of kd-trees, called rank-based kd-trees, for sets of points in~$Reals^d$. We show that a rank-based kd-tree, like an ordinary kd-tree, supports range search que-ries in~$O(n^{1-1/d}+k)$ time, where~$k$ is the output size. The main advantage of rank-based kd-trees is that they can be efficiently kinetized: the KDS processes~$O(n^2)$ events in the worst case, assuming that the points follow constant-degree algebraic trajectories, each event can be handled in~$O(log n)$ time, and each point is involved in~$O(1)$ certificates. We also propose a variant of longest-side kd-trees, called rank-based longest-side kd-trees (RBLS kd-trees, for short), for sets of points in~$Reals^2$. RBLS kd-trees can be kinetized efficiently as well and like longest-side kd-trees, RBLS kd-trees support nearest-neighbor, farthest-neighbor, and approximate range search queries in~$O((1/epsilon)log^2 n)$ time. The KDS processes~$O(n^3log n)$ events in the worst case, assuming that the points follow constant-degree algebraic trajectories; each event can be handled in~$O(log^2 n)$ time, and each point is involved in~$O(log n)$ certificates.
Cite as

Mohammad Abam, Mark de Berg, and Bettina Speckmann. Kinetic kd-Trees and Longest-Side kd-Trees. In Data Structures. Dagstuhl Seminar Proceedings, Volume 8081, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{abam_et_al:DagSemProc.08081.2,
  author =	{Abam, Mohammad and de Berg, Mark and Speckmann, Bettina},
  title =	{{Kinetic kd-Trees and Longest-Side kd-Trees}},
  booktitle =	{Data Structures},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8081},
  editor =	{Lars Arge and Robert Sedgewick and Raimund Seidel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08081.2},
  URN =		{urn:nbn:de:0030-drops-15307},
  doi =		{10.4230/DagSemProc.08081.2},
  annote =	{Keywords: Kinetic data structures, kd-tree, longest-side kd-tree}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact